class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> s;
        int pre = 0;
        int suf = 0;
        while (pre < pushed.size())
        {
            if (s.empty())
            {
                s.push(pushed[pre]);
                pre++;
            }
            if (s.top() == popped[suf])
            {
                s.pop();
                suf++;
                continue;
            }
            else
            {
                s.push(pushed[pre]);
                pre++;
            }
        }
        while (!s.empty())
        {
            if (s.top() == popped[suf])
            {
                s.pop();
                suf++;
            }
            else {
                break;
            }
        }
        if (s.empty())
        {
            return true;
        }
        return false;
    }
};